package org.example.myleet.p1034;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    /**
     * BFS，用队列记录待访问的连通分量的位置
     * 用一个和grid大小一样的visited数组记录访问位置，然后从起点开始通过广度优先遍历找到所有连通分量，对连通分量的每一个位置分析其是否边界
     */
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        //题目要求每个点的连通分量可能向四个方向延伸
        int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        int m = grid.length, n = grid[0].length;
        int originColor = grid[row][col];
        //visited数组记录访问位置，防止重复访问
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        List<int[]> borderList = new ArrayList<>();
        //加入起点
        queue.offer(new int[]{row, col});
        visited[row][col] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                //拉出下一个连通分量位置
                int[] nextP = queue.poll();
                boolean border = false;
                for (int j = 0; j < 4; ++j) {
                    //向4个方向探索相邻位置
                    int r = nextP[0] + directions[j][0], c = nextP[1] + directions[j][1];
                    if (0 <= r && r < m && 0 <= c && c < n && !visited[r][c]) {
                        //不越界且未访问情况下
                        if (originColor == grid[r][c]) {
                            //颜色和起点一致的位置是一起的连通分量
                            queue.offer(new int[]{r, c});
                            visited[r][c] = true;
                        } else {
                            //某个连通分量的4个方向中，其中一个方向不属于连通分量，因此当前位置是连通分量的边界
                            border = true;
                        }
                    }
                }
                if (nextP[0] == 0 || nextP[0] == m - 1 || nextP[1] == 0 || nextP[1] == n - 1) {
                    //或者当前位置位于整个grid的边界上，也算作连通分量的边界
                    border = true;
                }
                if (border) {
                    //加入到边界描绘数组中
                    borderList.add(nextP);
                }
            }
        }
        for (int[] p : borderList) {
            //给边界着色
            grid[p[0]][p[1]] = color;
        }
        return grid;
    }
}
